\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{listings}

\lstset{language=R, basicstyle=\footnotesize, breaklines=true}

\begin{document}
\author{Erik Fast, Quan Lam, Zhuoyu Li, Kyle Tiffany}
\title{Modeling Staffing and Arrivals at Husky Stadium\thanks{Math 381, Fall quarter, Patrick Perkins}}
\date{\today}

\maketitle

\begin{abstract}
	At Husky Stadium it is a challenge getting most of the fans into the stadium before the game starts while keeping staffing to a minimum. We model the stadium with a Monte Carlo simulation in order to determine the efficacy of current staffing levels as well as possible improvements. There are employees who search bags and those who do not. Our model takes this into account for six different gates and simulates how many fans are ``building up'' at each gate before the game. We find that the stadium is currently over-staffed and formulate a more efficient assignment. Our results can be extended to produce a more optimal result by taking into account ratios of bag to non-bag staff and the number of fans who are carrying bags.
\end{abstract}

\section{Introduction}
Football games at Husky Stadium present a difficult and interesting scheduling/queueing problem. A limited number of staff must check tickets and shepherd tens of thousands of people into the stadium within a few hours. On top of this, many fans carry personal items into the stadium, requiring that each gate dedicate a certain number of employees to searching bags.

Scheduling problems abound in operations research. A review \cite{ernst2004} lists ten different areas of application from venue management to manufacturing to hospitality and tourism. Exact solutions also tend to be difficult to find, since scheduling problems often translate into NP-Hard problems like set covering and Integer Programming. However, approximate solutions are usually good enough. In \cite{mason1998}, the authors use a mix of greedy algorithms and Integer Programming to find near-optimal solutions to staff scheduling problems at Auckland International Airport in New Zealand.

We will use a Monte Carlo simulation to determine how well staffing assignments perform based on data from various Husky games.

\section{Data}
UW Event Management \cite{gohuskies, huskystadium} provided us with their staff assignments and ticketing data. The staff assignments are broken into thirty-minute intervals and indicate how many bag checkers and non-bag checkers there are at each gate. The ticketing data indicates the total number of fans entering each gate (Table \ref{table:gates}) as well as the number of fans entering the stadium at fixed time intervals before the game starts (Table \ref{table:intervals}). That is, the games may start at different times, but we treat ``five minutes before kickoff'' as the same time interval for all games. In addition, the average total attendance based on the data is 53644 ($\sigma=6905.7$).

We also took data by hand at one of the games to find out the rate at which employees can admit ticketholders, depending on whether they are checking bags or not (Table \ref{table:bags}).

\begin{table}[here]
	\center
	\caption{Expected number of fans to enter through each gate (average over 3 games)}
	\begin{tabular}{|c|c|c|}
		\hline
		Gate & Total & $\sigma$ \\ \hline
		South & 3763 & 802.46 \\ \hline
		Southwest & 2811 & 239.56 \\ \hline
		West & 12587 & 1379.46 \\ \hline
		Northwest & 9593 & 497.41 \\ \hline
		North & 5864 & 1806.90 \\ \hline
		Student & 2034 & 311.85 \\ \hline
	\end{tabular}
	\label{table:gates}
\end{table}

\clearpage

\begin{table}[here]
	\center
	\caption{Expected number of fans entering the stadium in a given time interval (average over 3 games)}
	\begin{tabular}{|c|c|c|c|}
		\hline
		Interval & Minutes Before / After & Admitted & $\sigma$ \\ \hline
		1 & 60--55 & 1227 & 583.14 \\ \hline
		2 & 55--50 & 1487 & 638.28 \\ \hline
		3 & 50--45 & 1550 & 485.03 \\ \hline
		4 & 45--40 & 2007 & 672.50 \\ \hline
		5 & 40--35 & 2351 & 806.59 \\ \hline
		6 & 35--30 & 2602 & 1014.87 \\ \hline
		7 & 30--25 & 3136 & 1143.98 \\ \hline
		8 & 25--20 & 3634 & 1199.12 \\ \hline
		9 & 20--15 & 3950 & 1021.84 \\ \hline
		10 & 15--10 & 4290 & 793.72 \\ \hline
		11 & 10--5 & 4398 & 197.16 \\ \hline
		12 & 5--0 & 4137 & 307.95 \\ \hline
		13 & 0--5 & 3676 & 931.54 \\ \hline
		14 & 5--10 & 2839 & 1081.04 \\ \hline
		15 & 10--15 & 2030 & 864.67 \\ \hline
	\end{tabular}
	\label{table:intervals}
\end{table}

\begin{table}[here]
	\center
	\caption{Number of fans admitted with and without bags over a 40 minute period (Colorado game)}
	\begin{tabular}{|c|c|c|}
		\hline
		& Bags & No Bags \\ \hline
		\# of Lines & 12 & 3 \\ \hline
		\# of Staff & 27 & 3 \\ \hline
		\# Admitted per Line & 390 & 505 \\ \hline
	\end{tabular}
	\label{table:bags}
\end{table}

\section{Model}
The number of arrivals to occur in a given interval follow the $\text{Poisson}(\lambda)$ distribution, where $\lambda$ is the expected number of arrivals (\cite{winston}, Section 20.2). The hour before kickoff and 15 minutes after are split into 15 five-minute intervals. We model the total number of arrivals during interval $i$ as a Poisson random variable where $\lambda_i$ is the corresponding value in Table \ref{table:intervals}. We assume that the proportion of arrivals at a gate for one interval is the same as the total proportion $p_g$ of fans entering through that gate during the entire game. Based on the data in Table \ref{table:bags}, we assume that a single bag employee can admit on average 21.7 people in 5 minutes, and that a single non-bag employee can admit 63.1 people. If there are $b_g$ bag employees and $n_g$ non-bag employees at gate $g$, then the flow $f_g = 21.7b_g + 63.1n_g$ is the number of people that can be admitted through gate $g$ in a single interval.

Given an initial staffing assignment (i.e.\ the number of bag and non-bag employees at each gate), the following algorithm simulates arrivals and keeps track of the people building up at each gate after each time interval.

\begin{algorithm}[here]
	\begin{algorithmic}
		\STATE $\text{residual} \gets 0$
		\FOR{$i = 1 \to 15$}
			\STATE $\text{totalArrivals} \gets \text{RandomPoisson}(\lambda_i)$
			\STATE $\text{gateArrivals} \gets p_g \cdot \text{totalArrivals} + \text{residual}$
			\STATE $\text{residual} \gets \text{Max}(0,\ \text{gateArrivals} - f_g)$
		\ENDFOR
		\RETURN residual
	\end{algorithmic}
\end{algorithm}

In particular, in R we initialize the flow $f_g$ as follows

\begin{lstlisting}
gate.flow <- bag.employees * entries.per.bag.employee + nonbag.employees * entries.per.nonbag.employee
\end{lstlisting}

\noindent
and then for each interval we generate a random number of arrivals and add the previous residual

\begin{lstlisting}
for (expected in total.expected)
{
  total.arrivals <- rpois(n=1, lambda=expected)
  gate.arrivals <- gate.proportions * total.arrivals + residual
\end{lstlisting}

\noindent
and then subtract the flow from the arrivals to generate the new residual

\begin{lstlisting}
  residual <- gate.arrivals - gate.flow
\end{lstlisting}

\noindent
We then take the max of this and 0 to prevent negative residuals. Finally, we run this method many times and take an average to get the result, which is a vector with the residuals for the six gates.

\section{Results}
Using one of the staffing assignments given by UW Event Management as a starting point, we ran the simulation 10000 times for various levels of attendance. One such assignment is listed in Table \ref{table:staffing}.

\begin{table}[here]
	\center
	\caption{Initial staffing assignment for high attendance}
	\begin{tabular}{|c|c|c|}
		\hline
		Gate & Bags & No Bags \\ \hline
		South & 15 & 2 \\ \hline 
		Southwest & 12 & 2 \\ \hline 
		West & 37 & 5 \\ \hline 
		Northwest & 19 & 3 \\ \hline 
		North & 21 & 3 \\ \hline 
		Student & 16 & 2 \\ \hline 
	\end{tabular}
	\label{table:staffing}
\end{table}

When we use this initial staff assignment in our model, the result has a noticeable amount of unsatisfied customers, mainly at the West and Northwest gates.

Based on the result we got from directly counting fans at the entrances, we got a range for the proportion of customers with bags which is between 66\% and 80\% at various points in time. Since there is no way to predict how many fans would bring a bag with them, we choose to work with the average proportion of 75\%. The current ratio between ticketing and bag employees clearly is not tailored for this ratio. Since checking bags took on average three times longer than checking ticketing, it is plausible to use a ratio of 90\% staff checking bags and 10\% staff checking tickets. With this ratio, surprisingly there is almost no residual.

This means that the stadium is over-staffed. We move on to the next step, reducing the number of employees as much as we can while keeping the residuals near 0.

We wrote a program to reduce the number of employees at each gate gradually and stop when it is about to raise the residuals above 0, and also to add more staff to gates that have a residual. We do so for two scenarios: average attendance and high attendance.

\begin{table}[here]
	\center
	\caption{Improved staffing for average attendance}
	\begin{tabular}{|c|c|c|}
		\hline
		Gate & Bags & No Bags \\ \hline
		South & 10 & 1 \\ \hline 
		Southwest & 7 & 1 \\ \hline 
		West & 30 & 1 \\ \hline 
		Northwest & 23 & 3 \\ \hline 
		North & 14 & 2 \\ \hline 
		Student & 9 & 1 \\ \hline 
	\end{tabular}
\end{table}

\begin{table}[here]
	\center
	\caption{Improved staffing for high attendance}
	\begin{tabular}{|c|c|c|}
		\hline
		Gate & Bags & No Bags \\ \hline
		South & 11 & 1 \\ \hline 
		Southwest & 9 & 1 \\ \hline 
		West & 34 & 4 \\ \hline 
		Northwest & 26 & 3 \\ \hline 
		North & 15 & 2 \\ \hline 
		Student & 11 & 1 \\ \hline 
	\end{tabular}
	\label{table:revised_staffing}
\end{table}

In particular, we were able to reduce staff members by 25 in the high attendance case, and 38 in the average attendance case without incurring any additional residual at any of the gates.

\section{Conclusion}
There are many ways that the model can be improved. For one, it relies on admittance figures to generate arrival times. The number of fans admitted might give us a rough idea of how many people are arriving at a certain time, but the two are different things. Data about the actual arrivals would make the model more accurate, or queueing theory could be used.

Another factor that our model neglects is the proportion of bag-carrying fans. As it stands, replacing 3 bag employees with 1 non-bag employee will achieve roughly the same flow through the gate. However, this is obviously false in reality. If there are too many bag-carrying fans, it will reduce the flow. If there aren't many, then it will increase it. We did not have any bag/non-bag data, but having it would also improve the accuracy of the model.

We hope that our final result will be helpful to Husky Stadium. Especially considering that they are undergoing rennovations next year, good data on staffing could affect construction and management decisions. The model is not perfect, but our revised staffing result shows that there is room for improvement, and indicates which gates may benefit the most from staff reduction.

\bibliographystyle{plain}
\bibliography{paper}

\section*{Project contributions}
\begin{itemize}
	\item Erik Fast --- I wrote the initial model and R implementation. I also did the typesetting for this paper.
	\item Quan Lam --- I contributed in building of the model and analyzing the data to use with it together with the team. I help the team coming up with the testing plan and the use of different staffing ratio and different scenarios for testing purpose, and the strategies to use to optimize staff using the simulation. I wrote the code for simulating different combination of staffing ratio, different number of staff with different game attendance rate, run them and collected the result for conclusion.
	\item Zhuoyu Li --- I examined the data and computed some of the parameters used in our model. I modified the R code to implement our idea of optimization into the model and found out the conclusion that the original assignment was overstaffed. I also found one possibility of the optimal solution and suggested further improvement can be done.
	\item Kyle Tiffany --- My contribution to the project was very logistical in nature.  The first kernel of a topic was taken from my initial ideas, though Quan, Erik, and Zhouyu did a lot of the heavy lifting shaping it into a real project. I set up the meetings with Husky Athletics, our partner organization, and collected data by hand at Husky games.  I also assembled the presentation from slides given to me by my teammates.
\end{itemize}

\section*{Appendix}

Here we list the R code we used to implement the model.

\lstinputlisting{../code/husky.r}

\end{document}